//: [Previous](@previous)

/*:
 # 归并排序
 * 最好情况 O(nLogn))
 * 最坏情况 O(nLogn))
 * 平均时间复杂度 O(nLogn))
 * 空间复杂度 O(n)
 
 1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
 2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
 3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
 4. 重复步骤 3 直到某一指针达到序列尾；
 5. 将另一序列剩下的所有元素直接复制到合并序列尾。
 
 */

import Foundation

var numbers = [3, 6, 5, 2, 7, 9, 1, 4, 3]
print("排序前 \(numbers)")

func mergeSort(_ arr: [Int]) -> [Int] {
    if arr.count < 2 {
        return arr
    }
    
    let left = Array(arr[0..<arr.count/2])
    let right = Array(arr[arr.count/2..<arr.count])
    return merge(left: mergeSort(left), right: mergeSort(right))
}

func merge(left: [Int], right: [Int]) -> [Int] {
    var i = 0, j = 0
    
    var nums: [Int] = []
    
    while i < left.count && j < right.count {
        if left[i] < right[j] {
            nums.append(left[i])
            i += 1
        } else {
            nums.append(right[j])
            j += 1
        }
        
        if i >= left.count {
            nums += Array(right[j..<right.count])
            break
        }
        
        if j >= right.count {
            nums += Array(left[i..<left.count])
            break
        }
    }
    return nums
}

print("归并排序后 \(mergeSort(numbers))")

//: [Next](@next)
